Real-world decisions involve preferences that are nonlinear and often defined over multiple and interdependent issues. Such scenarios are known to be challenging, especially in strategic encounters between agents having distinct constraints and preferences. In this case, reaching an agreement becomes more difficult as the search space and the complexity of the problem grow. In this paper, we propose a new representation for constraint-based utility spaces that can tackle the scalability problem by efficiently finding the optimal contracts. Particularly, the constraint-based utility space is mapped into an issue-constraint hyper-graph. Exploring the utility space reduces then to a message passing mechanism along the hyper-edges by means of utility propagation. We experimentally evaluate the model using parameterized random nonlinear utility spaces. We show that it can handle a large family of complex utility spaces by finding the optimal contract(s), outperforming previous sampling-based approaches.